#include "main/utils.h"
using namespace std;

void genParethesisCore(int left, int right, string result, vector<string>& results) {
  if (left == 0 && right == 0) {
    results.push_back(result);
    return;
  }
  if (left > 0) {
    genParethesisCore(left - 1, right, result + "(", results);
  }
  if (left < right) {
    genParethesisCore(left, right - 1, result + ")", results);
  }
}

vector<string> genParenthesis(const int& n) {
  vector<string> results;
  string result;
  genParethesisCore(n, n, result, results);
  return results;
}

int main() {
  int n = 3;
  auto ret = genParenthesis(n);
  for (auto ele : ret) {
    cout << ele << endl;
  }

  return 0;
}
